#!/usr/bin/env python
# -*- coding: UTF-8 -*-
'''
@Project ：PythonData 
@File    ：case8_Cycle.py
@Author  ：朱志文
@Date    ：2021/11/2 8:14 
'''
# sum=0;
# item=1;
# itemDenominator=1;
# flag=1;
# while abs(item)>=1e-4:
#     sum+=item;
#     flag=-flag;
#     itemDenominator+=2;
#     item=1/itemDenominator*flag;
# print('%.10f'%(4*sum))

# sum=0;
# count=1;
# flag=1;
# while True:
#     item=flag/(2*count-1)
#     sum+=item;
#     count+=1;
#     flag=-flag;
#     if abs(item)<1e-6:
#         break;
# print('%.6f'%(sum*4))

'''判断一个数是不是素数'''
# m = int(input())
# flag = 1;
# for i in range(2, m):
#     if m % i == 0:
#         print('{num}不为素数'.format(num=m))
#         flag = -1;
#         break;
# if flag == 1:
#     print('{num}是素数'.format(num=m))

# import math as m;
#
# while True:
#     n = eval(input())
#     if n < 2:
#         print('%不是素数' % n)
#     else:
#         f = True;
#         for i in range(2, m.ceil(m.sqrt(n) + 1)):
#             if n % i == 0:
#                 f = False;
#                 break;
#         print('%d是素数' % n if f else '%d不是素数' % n)
#
# count=0
# for i in range(10,100):
#     g=i%10;
#     s=i//10;
#     reversal=g*10+s;
#     if i-reversal==27:
#         count+=1
#         print(count,i,reversal)
# print(count)


'''水仙花'''
# for i in range(100,999):
#     g=i%10;
#     s=i//10%10;
#     b=i//100;
#     if g**3+s**3+b**3==i:
#         print("水仙花数为{num}".format(num=i))

'''acm循环综合练习'''

'''
题目描述
完全数，又称完数、完美数或完备数，是一些特殊的自然数：它所有的真因子（即除了自身以外的约数）的和，恰好等于它本身。 
    例如：自然数6，它有约数1、2、3、6，除去它本身6外，其余3个数相加，1＋2＋3＝6 
    又如 自然数28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1＋2＋4 + 7 + 14＝28 
    所以，6和28是完全数。此外，还有496、8128也是完全数。 
    而对于自然数16，除去它本身16外，其余的约数相加，1＋2＋4＋8＝15，所以16不是完全数。

输入
正整数N（N≤10000）

输出
是否为Perfect Number，是的话输出Yes

不是的话输出No'''

# N = int(input())
# sum = 0;
# if N<=10000:
#     for i in range(1,N):
#         if N % i == 0:
#             sum+=i;
#     if sum==N:
#         print("Yes")
#     else:
#         print('No')

'''题目描述
有一个分数序列：2/1, 3/2, 5/3, 8/5, 13/8, …编写程序求出这个序列的前n项之和。

输入
输入只有一个正整数n，1≤n≤30。

输出
输出改序列前n项和，结果保留小数后6位。'''
# n = int(input())
# numerator = 2;
# denominator = 1;
# sum = 0;
# if 1 <= n <= 30:
#     for i in range(1, n + 1):
#         sum = numerator / denominator + sum;
#         numerator, denominator = numerator + denominator, numerator;
# print('%.6f' % sum)


'''题目描述
已知数列

a1=1

a2=1+2

a3=1+2+3

a4=1+2+3+4
......
输入正整数n（n≤100），计算a1+a2+a3+a4+......+an的累加和并输出。

样例输入 Copy
5
样例输出 Copy
35'''

# n = int(input())
# sum = 0;
# item = 0
# if n <= 100:
#     for i in range(1, n + 1):
#         item = item + i;
#         sum += item;
#     print(sum)


'''题目描述
如果我们列出10以下所有是3或5的倍数的自然数，我们得到3、5、6和9。这些倍数的总和是23。
给出一个自然数N，求N以下所有3或5的倍数的总和。
输入
输入一个自然数N ( N ≤ 60000 )
输出
打印答案。
样例输入 复制
10
样例输出 复制
23'''
# N = int(input())
# sum = 0;
# if N <= 60000:
#     for i in range(N):
#         if i % 3 == 0:
#             sum += i;
#         elif i % 5 == 0:
#             sum += i;
#     print(sum)

'''
题目描述
输入正整数n（0<n<10），计算∑n!=1!+2!+3!+...+n! 
要求：由于阶乘的结果比较大，按浮点数格式输出计算结果，有效数值保留一位小数点。 
样例输入 Copy
1
5
样例输出 Copy
1.0
153.0'''
# n = int(input())
# factorial = 1;
# result = 0;
# if 0 < n < 10:
#     for i in range(1, n + 1):
#         factorial *= i;
#         result += factorial;
#     print('%.1f'%result)


'''
题目描述
对于正整数N（N<1000000），如果N只能被1和N整除，则N为素数（质数），否则N为合数。

例如：自然数7，只能被7（它自己）和1整除，所以7是素数。 
      又如，自然数6，可以被1、2、3、6整除，所以6不是素数。 
输入
输入一个正整数N（N<1000000)

输出
如果输入数据为素数，则输出Yes；否则输出No

样例输入 Copy
【样例输入1】
2
【样例输入2】
73
【样例输入3】
119
样例输出 Copy
【样例输出1】
Yes
【样例输出2】
Yes
【样例输出3】
No'''

# N = int(input())
# flag = 1;
# if N<2:
#     print('No')
# else:
#     for i in range(2, N):
#         if N % i == 0:
#             flag = -1;
#             print('No')
#             break;
#     if flag == 1 :
#         print('Yes')


'''
题目描述
万里学院的教学楼有1号楼、3号楼、5号楼、53号楼等，门牌号尾号是奇数的教室在阳面，门牌号尾号是偶数的教室在阴面。例如，5201、53311在阳面，5202在阴面。

输入
第1行输入n(1≤n≤100)，表示n个教室的编号。

接下来输入n行，每行为1个教室的编号x（1000≤x≤99999）

输出
输出共有2行，第1行输出阳面教室的编号（2个教室编号用一个空格隔开），第2行表示阳面教室的个数。

样例输入 Copy
3
5201 
53311 
5202
样例输出 Copy
5201 53311
2'''
# n=int(input())
# list=[]
# listOdd=[]
# listEven=[]
# for i in range(n):
#     x=int(input())
#     list.append(x)
# for i in list:
#     if i %2==0:
#         listEven.append(i);
#     else:
#         listOdd.append(i)
# for i in listOdd:
#     print(i,end=' ')
# print()
# print(len(listOdd))

'''题目描述
请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。L、R在[2，99999]区间内。

例如，给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。

输入
输入共 1 行，为两个正整数 L 和 R，之间用一个空格隔开。

输出
输出共 1 行，表示数字 2 出现的次数。

样例输入 Copy
2 22
样例输出 Copy
6'''

# L, R = map(int, input().split())
# count = 0;
# for i in range(L, R + 1):
#     k = i;
#     while k > 0:
#         a = k % 10;
#         if a == 2:
#             count += 1
#         k = k // 10;
# print(count)

'''
题目描述
计算机2020级有n（n为整数，并且5≤n≤200）名学生，已知n名同学的考试成绩x（x为整数，并且0≤x≤100），求计算机2020级的平均分、最高分和最低分。
输入
输入有2行，第1行为学生人数n（n为整数，并且5≤n≤200）。
第2行为n名学生的成绩x（x为整数，并且0≤x≤100），2个成绩之间用空格隔开。
输出
输出计算机2020级的平均分、最高分和最低分，2个成绩之间用空格隔开。平均分保留2位小数，最高分和最低分均按整数输出。 '''

# n = int(input())
# list1 = []
# list1 = input().split()
# list2 = []
# i = 0
# sum = 0;
# while i < n:
#     m = int(list1[i])
#     list2.append(m)
#     i += 1
# min = list2[0];
# max = list2[0];
# sum = 0;
# for i in list2:
#     if i < min:
#         min = i;
#     elif i > max:
#         max = i;
#     sum += i;
# print('{avg} {max} {min}'.format(avg='%.2f' % (sum / len(list2)), max=max, min=min))

'''
题目描述
输入正整数n（2≤n≤1000000），将正整数N分解为素数因子的连乘式。

输入
测试数据只有1组，输入正整数n（2≤n≤1000000）。

输出
输出正整数N分解为素数因子的连乘式，见样例。'''

# n = int(input())
# while n != 1:
#     for index in range(2, n + 1):
#         if n % index == 0:
#             n = n // index;
#             if n == 1:
#                 print(index)
#             else:
#                 print('{}*'.format(index), end='')
#             break

'''
题目描述
有一个游戏叫“过7”，即从1开始数，当数到数字中包含7或者是7的倍数的数时跳过。
输入正整数n，试输出n以内没有跳过的数。 
输入
输入正整数n（1 ≤ n  ≤ 999）
输出
试输出n以内没有跳过的数。 注意每行输出15个数，每个数占4列并且右对齐。'''
# n=int(input())
# count=0;
# if 1<=n<=999:
#     for i in range(1,n+1):
#         if i%7!=0 and '7' not in str(i):
#             flag=1
#         else:
#             flag=0
#         if flag==1:
#             print('%4d'%i,end='')
#             count += 1;
#             if count%15 == 0:
#                 print()

'''题目描述
输入正整数A, B（0≤B≤A≤20），计算组合数

输入
测试数据只有1组

输出
每个输出占1行。'''
# import math
# A,B=map(int,input().split())
# if 0<=B<=A<=20:
#     print(math.factorial(A)//(math.factorial(B)*math.factorial(A-B)))

'''
题目描述
我们认为2是第一个素数，3是第二个素数，5是第三个素数，依次类推。
现在，给定两个整数n和m，0<n≤m≤300，你的程序要计算第n个素数到第m个素数之间所有的素数的和，包括第n个素数和第m个素数。
输入
输入两个整数，第一个表示n，第二个表示m。并且0<n≤m≤300
输出
一个整数，表示第n个素数到第m个素数之间所有的素数的和，包括第n个素数和第m个素数。'''

# n, m = map(int, input().split())
# sum = 0;  # 第n个素数到第m个素数的合
# count = 0;  # 记录素数的个数
# flag = 1;  # 假设某个数是素数
# x = 2;  # 第一个素数从2开始
#判断素数
# def isPrime(n):
#     for i in range(2, n):
#         if n % i == 0:
#             return 0
#             break;
#     else:
#         return 1;
#
#
# # 遍历前m个的素数
# while count < m:
#     # 判断一个数是否是素数
#     flag = 1;
#     flag = isPrime(x)
#     if flag == 1:
#         count += 1;
#         #如果是第n个素数则开始录入sum
#         if count >= n:
#             sum += x;
#     x += 1;
# print(sum)
